package internal.bucket;

import java.util.Arrays;

/**
 * @描述：桶排序适用于数据范围比较小的集合；桶排序是最快的排序，但是内存空间是最大的
 * @作者：hongxingfan
 * @时间：2014年9月5日 下午4:17:39
 */
public class BucketSort {

	public static void main(String[] args) {
//        int[] datas = { 19, 4, 1, 8, 7, 52, 2, 45, 30, 4, 6 };
		int[] datas = {4,6,1,5}; // 如果最大的那个数是1000，则需要int[1000]个数组（表示桶编号）
        // 桶排序
        bucketSort(datas, 0, 53);

        // 输出
        System.out.println(Arrays.toString(datas));
    }

	public static void bucketSort(int[] datas, int min, int max) {
		int length = datas.length;
		int[] tmp = new int[length];
		int[] bucket = new int[max - min];
		for (int i = 0; i < length; i++) {
			bucket[datas[i] - min]++;
		}
		// 这是最难理解的一步；i!=0就是datas中的元素，bucket[i]的值就是datas中元素的位置
		for (int i = 1; i < max - min; i++) {
			bucket[i] = bucket[i] + bucket[i - 1];
		}
		System.arraycopy(datas, 0, tmp, 0, length);
		/*
		 * 这就是算法，走了另一条思路，它不同于数据结构
		 * ------------------------------------
		 * |0,1,2,3,4,5,6 桶编号，也是数字
		 * |-------------
		 * |0,1,1,1,2,3,4 桶编号（数字），所在数组中的索引位置
		 */
		for (int i = length - 1; i >= 0; i--)
			datas[--bucket[tmp[i] - min]] = tmp[i];
	}
}
